package leetcode_2401_2500;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class LeeCode_2438 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(productQueries(15, new int[][]{{0,1},{2,2},{0,3}})));
    }
    private static int[] productQueries(int n, int[][] queries) {
        List<Integer> list = new ArrayList<>();
        while (n > 0){
            int l = 0, r = 100;
            while (l < r){
                int m = (l + r + 1) / 2;
                if (Math.pow(2, m) > n){
                    r = m - 1;
                }else {
                    l = m;
                }
            }
            list.add((int) Math.pow(2, l));
            n -= Math.pow(2, l);
        }
        list.sort(Comparator.comparingInt(o -> o));
        long mod = 1000_000_000 + 7;
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            long tmp = 1;
            for (int j = queries[i][0]; j <= queries[i][1]; j++) {
                tmp *= list.get(j);
                tmp %= mod;
            }
            ans[i] = (int) tmp;
        }
        return ans;
    }
}
